package com.zhugang.week08;

import java.util.*;

/**
 * @program algorithms
 * @description: letterCombinations
 * @author: chanzhugang
 * @create: 2022/08/04 20:50
 */
public class LetterCombinations {

    /**
     * 17 电话号码的字母组合
     *
     * @param digits
     * @return
     */
    private List<String> result = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) {
            return result;
        }
        String[] mappings = new String[10];
        mappings[2] = "abc";
        mappings[3] = "def";
        mappings[4] = "ghi";
        mappings[5] = "jkl";
        mappings[6] = "mno";
        mappings[7] = "pqrs";
        mappings[8] = "tuv";
        mappings[9] = "wxyz";

        char[] path = new char[digits.length()];
        backtrack(mappings, digits, 0, path);
        return result;
    }

    /**
     * @param mappings
     * @param digits   digits[k] + mappings 确定当前阶段的可选列表
     * @param k        阶段
     * @param path     路径
     */
    private void backtrack(String[] mappings, String digits, int k, char[] path) {
        if (k == digits.length()) {
            result.add(new String(path));
            return;
        }

        // 如：abc
        String mapping = mappings[digits.charAt(k) - '0'];
        for (int i = 0; i < mappings.length; i++) {
            path[k] = mapping.charAt(i);
            backtrack(mappings, digits, k + 1, path);
        }
    }
}